#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define ROW 5
#define COLUMN 5
typedef struct node
{
    int x;
    int y;
    int status;
    struct node *next;
} NODE;
// status意义：0表示孤立点或连通区域起点，其他数字表示与此点与多少个已有连通区域相连
//            若大于一，则需合并
NODE *Unit[4][ROW * COLUMN];
int a[ROW][COLUMN];                         // = {{1, 2, 1, 1, 4}, {4, 2, 3, 3, 1}, {3, 4, 3, 1, 1}, {2, 1, 1, 1, 4}, {4, 4, 2, 1, 4}};
int connect(int x1, int y1, int x2, int y2) //判断两点是否连通
{
    if (x1 == x2)
    {
        if (((y1 + 1 == y2) && (y1 + 2 <= COLUMN)) || ((y1 - 1 == y2) && (y1 - 1 >= 0)))
            return 1;
        else
            return 0;
    }
    if (y1 == y2)
    {
        if (((x1 + 1 == x2) && (x1 + 2 <= ROW)) || ((x1 - 1 == x2) && (x1 - 1 >= 0)))
            return 1;
        else
            return 0;
    }
    return 0;
}

void Append(NODE *L, int x, int y, int status) //在链表L最后插入元素
{
    NODE *p = L;
    while (p->next)
    {
        p = p->next;
    }
    NODE *new_node;
    new_node = (NODE *)malloc(sizeof(NODE)); //插入新节点
    new_node->x = x;
    new_node->y = y;
    new_node->status = status;
    new_node->next = NULL;
    p->next = new_node;
}

void find_connect(int x, int y)
{
    int status = 0; //是否已有连通块
    NODE *p;
    int i;
    for (i = 0; i < ROW * COLUMN && Unit[a[x][y] - 1][i]->next; i++)
    {
        p = Unit[a[x][y] - 1][i];
        p = p->next;
        while (p)
        {
            if (connect(x, y, p->x, p->y))
            {
                status++;
                Append(Unit[a[x][y] - 1][i], x, y, status);
            }
            p = p->next;
        }
    }
    if (status == 0)
    {
        Append(Unit[a[x][y] - 1][i], x, y, status);
        i++;
    }
}
void Combine(NODE *L1, NODE *L2)
{
    NODE *p = L1;
    NODE *q = L2->next;
    while (p->next)
    {
        p = p->next;
    }
    p->next = q;
    L2->next = NULL;
}
int walk(NODE *L) //打印
{
    NODE *p = L;
    int length = 0;
    p = p->next;
    while (p)
    {
        p = p->next;
        length++;
    }
    p = L;
    p = p->next;
    if (length >= 2)
    {
        while (p)
        {
            if (p->status <= 1)
            {
                printf("(%d,%d) ", p->x + 1, p->y + 1);
            }
            p=p->next;
        }
        printf("\n");
    }
    
    return length;
}
int main()
{
    int i, j;
    srand((unsigned)time(NULL));
    for (i = 0; i < ROW; i++)
    {
        for (j = 0; j < COLUMN; j++)
        {
            a[i][j] = rand() % 4 + 1;
            if(a[i][j]==1)
            printf("\33[31m%d \33[0m", a[i][j]);
            if(a[i][j]==2)
            printf("\33[32m%d \33[0m", a[i][j]);
            if(a[i][j]==3)
            printf("\33[33m%d \33[0m", a[i][j]);
            if(a[i][j]==4)
            printf("\33[34m%d \33[0m", a[i][j]);
        }
        printf("\n");
    }
    for (i = 0; i < 4; i++)
    {
        for (j = 0; j < ROW * COLUMN; j++)
        {
            Unit[i][j] = (NODE *)malloc(sizeof(NODE));
            Unit[i][j]->x = 0;
            Unit[i][j]->y = 0;
            Unit[i][j]->status = 0;
            Unit[i][j]->next = NULL;
        }
    }
    for (i = 0; i < ROW; i++)
    {
        for (j = 0; j < COLUMN; j++)
        {
            find_connect(i, j);
        }
    }
    NODE *p, *q;
    for (int k = 0; k < 4; k++) //去重
    {
        for (i = 0; i < ROW * COLUMN && Unit[k][i]->next; i++)
        {
            p = Unit[k][i]->next;
            while (p)
            {
                if (p->status > 1)
                {
                    for (j = 0; j < i; j++)
                    {
                        q = Unit[k][j]->next;
                        while (q)
                        {
                            if (p->x == q->x && p->y == q->y && q->status <= 1)
                            {
                                Combine(Unit[k][i], Unit[k][j]);
                            }
                            q = q->next;
                        }
                    }
                }
                p = p->next;
            }
        }
    }
    for (i = 0; i < 4; i++)
    {
        printf("Color%d:\n", i + 1);
        for (j = 0; j < ROW * COLUMN; j++)
        {
            if (Unit[i][j]->next)
                walk(Unit[i][j]);
        }
    }
    return 0;
}